Conventional computers are comprised of millions of transistors which operate as "switches" that can be either turned "on" or turned "off." When a transistor is turned on or conducting, it is said to represent one state (i.e., "1"); and when the transistor is turned off or non-conducting, it represents another state (i.e., "0"). Thereby, the state of a transistor can be used to represent a bit of data (i.e., 0 or 1). Individual transistors are interconnected to form gates for performing digital logic functions. A computer program instructs the logic to perform a given algorithm on a set of given inputs. By controlling the switching of these transistors millions of times per second, a computer can perform the steps of a programmed algorithm very rapidly. For example, a computer can easily be programmed to multiply two numbers together and attain the result almost instantaneously (e.g., 127.times.229=29083). Nevertheless, there are some problems which are very difficult to compute. This is due to the fact that the algorithms for solving these problems are very complicated and call for repeated iterations. For example, factorization is very difficult (e.g., given 29083 find A and B where A.times.B=29083). Recently, it took the combined processing power of approximately 1600 conventional workstations around the world eight months to factor a 129 digit number. Extrapolating, it would take approximately 800,000 years to factor a 250 digit number. While no efficient method is known for factoring large numbers, there exists no proof that efficient factorization is impossible. However, there exist problems known as "NP-complete" (e.g., 3SAT) that take an exponential amount of time to solve on a classical Turing machine. Simply increasing the speed or number of processors in conventional computers would minimally impact our ability to solve these NP-complete problems. Clearly, a radical new approach is needed if solutions posed by these sets of problems are to be efficiently solvable.
One possible solution envisioned in the future pertains to harnessing and applying the principles of quantum mechanics to performing computations. Such a "quantum" computer would theoretically be capable of solving NP-complete problems orders of magnitude faster than a conventional computer. Instead of using traditional bits, a quantum computer would operate on quantum mechanical bits (qubits). Unlike a traditional bit which is always a 0 or always a 1, the qubit can be in a state comprised of a combination or "superposition" of both 0 and 1. The superposition of the multiple states of a qubit is defined by a wave function. Due to the unique properties of wave functions and quantum mechanics, each of the superposition of states of qubits are capable of being processed simultaneously. Whereas a conventional N-bit computer performs N computations, an N-qubit quantum computer can perform 2.sup.N computations at the same time due to the quantum parallelism phenomenon. In other words, the processing power of a quantum computer increases exponentially as compared to linearly for a conventional computer. Thereby, problems which took exponential time to solve by a conventional computer would be capable of being efficiently solved in polynomial time by a quantum computer.
Unfortunately, the technology for building an actual physical, working quantum computer made up entirely of quantum circuits may be decades away. Some well respected scientists and physicists have questioned whether it is even possible to construct a useful quantum computer. See C. H. Bennett, D. P. DiVincenzo, "Progress Towards Quantum Computation," S. L. Braunstein, "Quantum Computation: A Tutorial," J. Preskill, "Quantum Computing: Pro and Con," Svozil, "First International Conference on Unconventional Models of Computation UMC '98, An Unconventional Review," and V. Vedral, M. B. Plenio, "Basics of Quantum Computation." The reason why it is so difficult to build a quantum computer is because the qubits, in their quantum superposition of states, exist in an extremely delicate and sensitive phase coherent balance. Any outside disturbance at all (e.g., simply observing the qubit), will cause the wave function collapse or "decohere" to a specific one of its several possible simultaneous states, in which case, all of the other states, along with the information represented therein, will be lost. Thus, the qubits must be isolated in order to preserve their quantum phase coherency. And yet, the qubits must somehow be loaded into the quantum computer with initial input conditions, controlled to perform specified functions, and then read out to find the final answer. It is these two seemingly contradictory constraints, which makes it extremely difficult to construct a quantum computer.
The present invention provides a novel, unique solution to this dilemma by accelerating a conventional computer with the addition of a few, small quantum devices ingeniously coupled to the conventional computer. The advantage of the present invention is that the conventional computer is readily available and is relatively inexpensive to program and maintain, but its processing power is exponentially increased by virtue of the quantum devices interacting with the conventional computer. Thereby, the bulk of this new hybrid quantum computer is comprised of a conventional computer with ordinary semiconductor circuits which do not need to kept in an isolated, phase coherent state. Yet, it has the full advantage of parallel, exponential quantum processing conferred by the few quantum devices. Furthermore, the present invention greatly minimizes the number of coupled qubits necessary for useful applications.